package lintcode;

import java.util.*;

/**
 * @author wq
 * 二叉树的前序遍历
 * 根->左->右
 */
public class BinaryTreePreorder {

}

class TreeNode {
      public int val;
      public TreeNode left, right;
      public TreeNode(int val) {
          this.val = val;
          this.left = this.right = null;
      }
}
class Solution{
    List<Integer> list=new ArrayList<>();

    /*
    递归解法
    * */
    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        if(root==null){
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
    /*
    非递归写法
    * */
    public List<Integer> preorderTraversa1(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        Deque<TreeNode> stack=new ArrayDeque<>();

        if(root==null){
            return res;
        }

        while (root!=null||!stack.isEmpty()){
            if(root!=null){
                res.add(root.val);
                stack.push(root);
                root=root.left;
            }else{
                root=stack.pop();
                root=root.right;
            }
        }

        return res;
    }
    /*
    非递归写法 仿深搜
    * */

}
